package hashtable;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author "随风Coding"          // 系统用户名（自动填充）
 * @email 1431471764@qq.com  // 替换为你的邮箱（固定或自定义变量）
 * @date 2025/8/19 09:48    // 创建日期和时间（自动填充）
 */
public class FourSum {


    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> siYuanZu = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        for (int k = 0; k < nums.length; k++) {
            //先对第一个数进行剪枝和去重
            if ((nums[k] > target) && nums[k] > 0)
                break;
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.length; i++) {
                //再对第二个数进行剪枝和去重
                if (nums[i] + nums[k] > target && nums[k] + nums[i] > 0)
                    break;
                if ((i > k + 1) && nums[i] == nums[i - 1])
                    continue;
                //固定前2个数后 要使用双指针对后2个数进行移动 再加以判断 符合条件的就加入四元组；然后再进行去重再进入下一次寻找
                int left = i + 1;
                int right = nums.length - 1;
                while (left < right) {
                    int sum = nums[k] + nums[i] + nums[left] + nums[right];
                    if (sum > target)
                        right--;
                    else if (sum < target) {
                        left++;
                    } else {
                        //找到了四元组 先存储 再去重left和 right
                        siYuanZu.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right]));
                        while (right > left && (nums[right] == nums[right - 1]))
                            right--;
                        while ((right > left) && (nums[left] == nums[left + 1]))
                            left++;
                        right--;
                        left++;
                    }
                }
            }

        }
        return siYuanZu;
    }

    public static void main(String[] args) {
        FourSum solution = new FourSum();
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        List<List<Integer>> results = solution.fourSum(nums, target);
        for (List<Integer> result : results) {
            System.out.println(result);
        }
    }
}
